/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package wordtree;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;
import reader.DicoReader;

/**
 *
 * @author nicolas
 */
public class WordTree implements DicoReader {
	
	private static Random random = new Random(System.currentTimeMillis());
	private static final int[][] stategies = {
		{20,15,3,21,19,6,8,2,16,13,9,11,7,18,5,25,1,0,10,17,23,14,4,12,24,22},
		{5,16,25,11,12,22,19,3,17,9,4,24,10,1,23,15,8,13,7,20,21,14,2,0,18,6},
		{2,10,18,7,23,9,14,12,11,0,22,16,24,13,20,4,19,21,5,8,17,3,25,1,15,6},
		{15,11,6,1,22,5,18,10,3,17,13,20,25,14,0,7,23,24,9,12,16,19,4,21,2,8},
		{14,18,9,8,17,11,12,10,13,6,22,7,0,21,24,19,2,25,4,20,16,5,1,3,15,23},
		{12,15,6,0,9,17,2,1,11,22,14,3,7,25,21,24,16,20,18,8,19,10,13,5,23,4},
		{25,5,18,22,0,7,12,20,10,3,2,13,21,4,17,9,19,15,1,11,24,16,23,8,6,14},
		{11,5,7,20,14,24,23,10,0,9,19,6,12,13,4,17,15,25,8,21,2,22,1,18,3,16},
		{3,17,4,12,9,7,15,1,6,22,10,24,2,8,23,20,21,14,25,19,18,5,13,16,0,11},
		{4,6,25,22,16,5,9,14,21,12,7,23,1,19,18,17,10,20,15,11,8,2,13,24,3,0},
		{2,24,19,7,17,13,15,5,1,20,4,23,21,25,9,10,12,22,14,11,18,6,16,8,3,0},
		{13,0,17,5,25,6,8,12,2,19,20,15,1,10,16,3,9,11,24,23,18,14,21,7,4,22},
		{11,5,4,21,17,24,12,15,19,8,0,14,3,20,16,6,10,13,25,9,22,7,1,23,18,2},
		{11,13,0,9,16,21,10,5,25,19,22,15,4,3,2,18,17,14,20,6,24,8,12,7,23,1},
		{4,19,8,21,22,0,6,18,10,23,20,15,5,14,17,1,9,24,13,12,25,11,2,3,16,7},
		{4,7,1,23,14,0,19,11,9,13,21,24,25,10,17,2,16,5,3,8,12,18,6,20,22,15},
		{4,5,9,3,24,25,2,6,17,10,0,20,12,16,19,22,13,23,14,7,11,21,18,1,15,8},
		{1,8,18,25,19,14,7,2,23,22,10,5,20,11,4,3,12,0,9,21,16,6,15,17,24,13},
		{25,18,3,9,12,1,0,14,4,17,20,6,21,23,2,15,10,16,24,11,8,19,7,5,22,13},
		{25,22,12,3,13,15,16,0,20,21,1,9,8,14,11,2,19,10,24,17,6,4,18,7,5,23},
		{23,16,11,10,8,22,21,14,7,25,19,24,4,20,18,12,2,6,1,9,5,0,13,17,3,15},
		{22,20,14,10,17,11,2,15,24,8,25,23,18,6,16,3,4,7,12,13,19,1,9,5,21,0},
		{0,3,12,14,11,23,9,6,2,15,22,25,10,18,20,13,19,8,4,24,7,5,17,21,16,1},
		{8,10,3,1,7,6,13,22,18,23,16,11,4,20,15,14,25,24,0,12,21,17,5,2,9,19},
		{21,3,9,16,20,5,18,19,13,24,2,4,1,7,25,22,23,14,11,0,10,6,17,15,8,12},
		{10,6,24,13,19,21,7,23,18,12,17,2,25,22,3,20,5,1,4,9,11,15,16,14,0,8},
		{5,19,1,12,22,20,17,25,8,4,7,0,2,18,6,21,10,11,23,16,14,9,13,3,24,15},
		{16,15,21,11,24,2,0,12,10,14,9,13,7,6,5,8,17,3,20,18,25,23,19,1,4,22},
		{23,17,4,9,14,21,1,20,13,7,16,12,25,0,10,2,3,19,15,11,8,6,24,22,5,18},
		{23,10,17,21,14,0,12,20,19,24,4,5,18,16,7,6,15,3,22,8,13,11,25,2,1,9},
		{18,10,17,4,22,13,24,7,14,0,16,21,11,12,3,20,19,15,8,25,5,1,6,23,9,2},
		{3,2,0,14,9,15,6,22,19,20,8,17,7,12,4,16,5,23,11,1,21,25,10,18,24,13},
		{2,23,12,0,21,9,15,25,20,17,18,10,19,11,5,24,7,1,13,16,22,8,6,3,14,4},
		{14,16,0,12,6,11,21,4,5,9,22,8,20,3,23,25,2,13,19,18,17,1,10,15,7,24},
		{24,16,5,3,12,11,9,22,20,0,7,19,18,1,13,23,15,2,17,6,21,14,10,8,4,25},
		{24,23,8,14,2,20,7,19,6,5,1,21,10,3,4,22,18,13,17,11,25,9,16,15,0,12},
		{7,21,20,6,14,3,8,10,4,24,17,13,9,2,5,1,12,11,22,19,18,25,16,23,15,0},
		{21,3,19,20,18,7,12,23,2,8,10,15,5,16,11,13,4,1,14,17,25,22,6,0,9,24},
		{2,5,7,22,11,19,13,15,24,20,17,21,1,25,8,10,3,14,0,18,16,23,12,6,9,4},
		{7,3,22,11,15,25,19,0,14,1,16,5,6,4,24,2,8,20,13,18,21,17,10,9,12,23},
		{16,19,1,12,14,9,17,11,20,2,24,0,18,15,13,3,7,6,4,21,22,10,25,8,5,23},
		{0,7,10,24,12,6,3,15,4,11,16,25,19,22,18,9,14,20,21,23,17,13,8,5,2,1},
		{3,8,21,9,12,2,0,14,11,5,7,10,20,23,6,22,4,19,18,13,24,15,16,1,25,17},
		{20,11,3,19,14,12,9,23,24,5,21,16,0,22,2,17,18,7,8,4,25,6,13,1,15,10},
		{8,5,24,14,2,17,16,9,6,11,18,4,22,3,25,0,12,20,7,21,23,19,1,13,10,15},
		{23,15,13,16,11,18,25,9,21,3,7,8,14,0,19,24,6,10,20,5,4,12,17,22,1,2},
		{23,11,6,12,25,4,24,20,5,14,21,15,7,8,16,22,1,19,10,0,9,2,17,18,3,13},
		{23,18,9,17,24,10,2,21,0,19,16,25,15,1,12,13,8,5,4,3,6,7,22,14,11,20},
		{7,11,8,25,1,4,12,24,21,22,14,9,0,13,15,23,17,6,16,20,18,2,5,19,3,10},
		{16,23,7,14,20,25,1,19,3,12,4,10,8,2,22,5,9,17,0,15,18,24,11,13,21,6},
		{24,13,20,8,1,22,17,12,3,11,7,25,21,14,19,9,16,18,5,23,4,10,2,15,0,6},
		{5,1,7,12,14,18,6,10,4,2,15,22,8,0,21,17,20,24,16,3,23,25,13,19,9,11},
		{10,11,13,19,16,2,14,3,17,15,21,8,7,4,18,6,5,0,22,23,1,20,9,12,24,25},
		{18,6,17,12,8,4,0,19,14,21,22,1,5,24,9,23,16,15,3,11,2,13,25,10,20,7},
		{17,24,2,14,11,22,23,6,12,4,20,13,15,19,18,1,3,5,21,8,0,10,9,16,25,7},
		{23,3,10,21,20,17,7,16,22,13,18,0,1,6,14,2,12,19,11,8,9,25,5,15,4,24},
		{12,13,2,11,14,21,16,24,22,4,0,6,5,10,1,17,7,18,9,25,3,15,8,23,20,19},
		{16,3,10,22,6,11,1,8,25,18,21,7,4,23,15,2,0,19,14,12,20,5,9,24,17,13},
		{8,3,7,10,16,19,12,17,0,5,6,21,22,9,20,13,11,15,23,4,18,25,14,2,1,24},
		{19,21,24,11,13,3,22,5,20,0,16,14,6,25,12,7,17,18,4,23,15,10,1,8,2,9},
		{24,3,20,6,2,16,5,13,7,25,4,18,10,12,15,22,0,21,9,1,17,23,19,11,14,8},
		{13,19,0,11,9,6,12,23,15,20,8,2,3,22,24,14,18,21,7,1,16,25,17,4,10,5},
		{16,9,10,4,7,15,13,20,11,17,21,1,3,14,23,25,12,22,18,6,0,2,8,19,24,5},
		{16,9,13,14,24,12,23,6,4,1,19,7,25,11,8,17,3,5,22,18,2,0,20,10,21,15},
		{17,12,20,9,10,8,14,1,16,19,13,5,0,15,2,11,18,24,25,7,23,4,22,3,6,21},
		{20,16,24,15,8,0,25,9,18,1,17,11,2,12,7,14,19,13,21,4,22,5,3,10,6,23},
		{23,1,24,6,22,25,11,4,10,16,7,19,20,14,17,21,5,18,3,12,2,13,9,0,15,8},
		{9,25,18,12,4,7,17,21,22,14,8,15,20,6,10,23,5,24,16,13,11,2,3,1,0,19},
		{12,15,8,19,18,13,20,25,23,2,16,5,6,4,14,21,3,0,22,7,10,9,17,1,24,11},
		{0,22,15,24,2,18,3,16,25,17,13,5,19,8,10,6,4,1,23,11,7,14,12,9,20,21},
		{8,20,11,23,5,7,10,0,25,24,2,3,17,1,22,12,13,14,18,19,21,4,16,6,15,9},
		{25,17,15,24,11,13,10,3,0,2,1,12,14,4,6,22,16,23,7,18,5,20,19,21,8,9},
		{0,1,24,21,23,16,18,15,3,8,22,12,6,7,4,5,25,13,17,2,11,19,10,9,14,20},
		{19,14,25,6,9,0,20,22,17,10,5,24,1,3,13,11,15,2,4,23,18,21,8,7,16,12},
		{15,20,11,1,9,3,14,2,25,17,24,18,8,12,21,16,13,19,4,6,22,5,0,23,7,10},
		{13,1,3,4,5,17,2,23,25,18,20,8,24,22,19,6,12,10,11,15,21,14,7,0,16,9},
		{21,2,5,9,16,8,6,10,0,7,3,4,18,13,19,25,20,1,14,24,12,23,11,17,22,15},
		{0,23,6,16,8,22,12,15,17,1,3,2,24,10,7,13,5,4,9,21,20,14,11,18,19,25},
		{17,8,12,24,14,19,21,16,22,13,0,9,1,7,20,10,23,2,15,25,5,3,4,6,11,18},
		{12,10,0,1,4,24,17,25,9,11,5,23,7,18,20,16,15,22,8,14,6,13,3,21,19,2},
		{5,2,24,21,8,0,19,17,10,18,25,7,23,13,14,11,15,20,3,6,9,22,12,4,16,1},
		{13,3,8,20,16,14,2,24,25,4,12,15,0,10,19,9,5,11,17,23,7,1,21,6,22,18},
		{15,25,11,22,20,6,19,2,18,13,7,5,9,0,3,4,24,21,17,8,1,10,12,23,14,16},
		{7,5,10,6,22,16,0,25,11,18,13,17,24,23,8,19,21,12,20,3,2,9,15,14,4,1},
		{13,20,9,14,24,15,10,23,8,5,6,11,0,25,7,17,4,16,3,18,2,1,22,19,21,12},
		{13,21,20,6,0,4,10,19,23,8,24,16,7,1,17,5,18,25,2,12,11,22,9,3,15,14},
		{11,3,25,5,4,8,18,22,16,21,2,0,19,17,10,13,1,15,9,24,20,14,12,23,6,7},
		{14,10,19,3,8,23,22,18,4,12,1,15,24,6,20,11,2,5,0,17,9,7,25,16,13,21},
		{23,4,3,22,19,21,8,17,1,20,14,10,11,7,24,16,13,2,18,6,9,25,15,12,0,5},
		{1,7,8,3,17,12,25,4,24,16,15,9,21,0,5,20,22,14,18,6,23,19,11,10,13,2},
		{2,15,21,11,10,14,12,16,24,23,18,5,25,8,22,7,0,17,19,6,3,13,4,9,1,20},
		{3,12,19,11,8,22,16,18,0,13,2,7,4,24,9,6,1,20,14,10,17,21,15,25,5,23},
		{19,20,22,13,21,23,17,24,4,2,18,14,9,6,3,25,5,12,11,7,8,15,1,16,10,0},
		{16,10,15,25,5,12,17,14,6,8,24,21,22,9,1,4,3,0,2,13,20,23,11,19,7,18},
		{0,7,10,17,6,5,23,18,4,24,8,25,11,14,19,12,16,1,22,21,9,3,13,20,15,2},
		{3,7,4,18,21,12,14,20,1,2,23,16,8,10,24,25,0,17,11,19,9,15,5,13,22,6},
		{6,5,25,13,1,16,4,9,20,24,18,2,8,10,7,21,22,11,12,19,3,23,0,17,14,15},
		{14,10,8,2,25,9,13,6,18,1,19,22,21,12,20,3,16,17,4,11,23,0,7,5,24,15},
		{7,5,9,2,16,20,6,24,1,8,17,18,13,21,3,19,25,14,15,22,4,11,0,10,12,23},
		{4,5,19,6,8,20,21,16,14,12,24,9,2,18,0,3,13,22,11,15,7,10,23,25,17,1}};

	public static final char WILDCARD = '.';
	private WordTree[] childs = null;
	private boolean isWord = false;

	private WordTree() {
	}

	public static WordTree fromFile(String dictPath) {
		InputStream is = null;
		try {
//			ArrayList<String> words = new ArrayList<String>();
			is = new FileInputStream(new File(dictPath));
			DataInputStream in = new DataInputStream(is);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String line;
			WordTree wt = new WordTree();
			while (br.ready() && (line = br.readLine()) != null) {
				wt.insert(line);
			}
			return wt;
		} catch (IOException ex) {
			Logger.getLogger(WordTree.class.getName()).log(Level.SEVERE, null, ex);
		} finally {
			try {
				is.close();
			} catch (IOException ex) {
				Logger.getLogger(WordTree.class.getName()).log(Level.SEVERE, null, ex);
			}
		}
		return null;
	}

	@Override
	public List<String> getMatchPattern(String pattern) {
		List<String> l = new ArrayList<String>();
		this.match(pattern, l, "");
		return l;
	}
	
	@Override
	public List<String> takeMatchPattern(String pattern, int howMany) {
		List<String> l = new ArrayList<String>();
		this.match(pattern, l, "", howMany);
		return l;
	}

	@Override
	public boolean hasAtLeastOnMatch(String pattern) {
		return null != this.matchOne(pattern, "");
	}
	
	private void match(String p, List<String> l, String prefix, int howMany) {
		if (p.length() == 0) {
			if (this.isWord) {
				l.add(prefix);
			}
			return;
		}
		char c = p.charAt(0);
		if (c == WILDCARD) {
			int idx;			
			int[] stategy = nextStrategy();
			for (int j = 0; j < 25 && howMany > l.size(); j++) {
				idx = stategy[j];
				if (childs != null && childs[idx] != null) {
					childs[idx].match(p.substring(1),
							l,
							prefix + new Character((char) (65 + idx)),
							howMany);
				}
			}
		} else {
			int idx = p.charAt(0) - 65;
			if (childs != null && childs[idx] != null && howMany < l.size()) {
				childs[idx].match(p.substring(1),
						l,
						prefix + new Character((char) (65 + idx)),
						howMany);
			}
		}
	}

	public void match(String p, List<String> l, String prefix) {
		if (p.length() == 0) {
			if (this.isWord) {
				l.add(prefix);
			}
			return;
		}
		char c = p.charAt(0);
		if (c == WILDCARD) {
			for (int j = 0; j < 25; j++) {
				if (childs != null && childs[j] != null) {
					childs[j].match(p.substring(1),
							l,
							prefix + new Character((char) (65 + j)));
				}
			}
		} else {
			int idx = p.charAt(0) - 65;
			if (childs != null && childs[idx] != null) {
				childs[idx].match(p.substring(1),
						l,
						prefix + new Character((char) (65 + idx)));
			}
		}
	}

	public String matchOne(String p, String prefix) {
		int[] stategy = nextStrategy();
		if (p.length() == 0) {
			if (this.isWord) {
				return prefix;
			} else {
				return null;
			}
		}
		char c = p.charAt(0);
		String r;
		int idx;
		if (c == WILDCARD) {
			for (int j = 0; j < 25; j++) {
				idx = stategy[j];
				if (childs != null && childs[idx] != null) {
					r = childs[idx].matchOne(p.substring(1), prefix + new Character((char) (65 + idx)));
					if (r != null) {
						return r;
					}
				}
			}
		} else {
			idx = c - 65;
			if (childs != null && childs[idx] != null) {
				return childs[idx].matchOne(p.substring(1), prefix + new Character((char) (65 + idx)));
			}
		}
		return null;
	}

	public boolean exists(String s) {
		if (s.length() == 0) {
			return this.isWord;
		}
		int idx = s.charAt(0) - 65;
		if (childs == null || childs[idx] == null) {
			return false;
		}
		return childs[idx].exists(s.substring(1));
	}

	public void insert(String s) {
		if (s.length() == 0) {
			this.isWord = true;
		} else {
			int idx = s.charAt(0) - 65;
			if (childs == null) {
				childs = new WordTree[26];
			}
			if (childs[idx] == null) {
				childs[idx] = new WordTree();
			}
			childs[idx].insert(s.substring(1));
		}
	}

	/**
	 * @param args the command line arguments
	 */
	public static void main(String[] args) {
		String dictPath = "dico2.ret";
		WordTree wt = WordTree.fromFile(dictPath);

		String pattern = ".....";
		int size = 0;
		
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < 1000; i++) {
			size = wt.getMatchPattern(pattern).size();
		}
		long stopTime = System.currentTimeMillis();
		long runTime = stopTime - startTime;
		System.out.println("Size : " + size);
		System.out.println("Run time: " + runTime + " ms");

		startTime = System.currentTimeMillis();
		for (int i = 0; i < 1000; i++) {
			size = wt.takeMatchPattern(pattern, 10).size();
		}
		stopTime = System.currentTimeMillis();
		runTime = stopTime - startTime;
		System.out.println("Size : " + size);
		System.out.println("Run time: " + runTime + " ms");
	}

	@Override
	public String getWildCard() {
		return String.valueOf(WILDCARD);
	}

	@Override
	public String getOneMatchPattern(String pattern) {
		return this.matchOne(pattern, "");
	}

	private int[] nextStrategy() {
		return stategies[random.nextInt(100)];
	}
}
